#include<iostream>
using namespace std;

struct Node {
public:
	int data;
	Node* next;
	Node* prev;
};

class DoubleLinkedList {
public:
	Node* pHead;

	//constructor
	DoubleLinkedList() {
		pHead = NULL;
	}

	void display() {
		Node* ptr = pHead;
		if (ptr == NULL)
			cout << "LIST NULL";
		else {
			while (ptr != NULL) {

				//if ptr is pHead
				if (ptr->prev == NULL) {
					if (ptr->next == NULL)
						cout << "NULL <- " << ptr->data << " -> NULL";
					else
						cout << "NULL <- " << ptr->data << " <-> ";
				}
				//if ptr is last
				else if (ptr->next == NULL) {
					cout << ptr->data << " -> NULL";
				}
				//others case
				else {
					cout << ptr->data << " <-> ";
				}
				ptr = ptr->next;
			}
		}
		cout << endl;
	}

	/*
	 * Add element to head of list
	 */
	void prepend(int data) {

		Node *pNew = new Node();
		pNew->next = NULL;
		pNew->prev = NULL;
		pNew->data = data;

		if (pHead == NULL)
			pHead = pNew;
		else {
			pNew->next = pHead;
			pHead->prev = pNew;
			pHead = pNew;
		}
	}

	/*
	 * Add element to last of list
	 */
	void pospend(int data) {

		if (pHead == NULL)
			prepend(data);
		else {
			Node* ptr = pHead;
			while (ptr->next != NULL)
				ptr = ptr->next;

			Node* pNew = new Node();
			pNew->data = data;
			pNew->next = NULL;
			pNew->prev = NULL;

			ptr->next = pNew;
			pNew->prev = ptr;
		}
	}

	/*
	 * Insert data to position index
	 */
	void insert(int data, int index) {
		cout << "Insert  " << data << " at index : " << index << endl;
		if (index == 0)
			prepend(data);
		else {
			Node* pNew = new Node();
			pNew->data = data;
			pNew->next = NULL;
			pNew->prev = NULL;

			Node* pt = pHead;
			for (int i = 0; i < (index - 1); i++)
				pt = pt->next;

			Node* ptNext = pt->next;
			pNew->next = ptNext;
			pNew->prev = pt;
			pt->next = pNew;
		}
	}

	/*
	 * Remove all node has value data in list
	 */
	void remove(int data) {

		Node* pCur = pHead;
		while (pCur != NULL) {

			/*
			 * Found a node have data need to be deleted
			 */
			if (pCur->data == data) {

				/*
				 * Remove from the begining of list
				 * Fix the begining pointer
				 */
				if (pCur->prev == NULL) {
					pHead = pCur->next;
					pCur->next->prev = NULL;
				}

				/*
				 * Remove from the end of list
				 */
				else if (pCur->next == NULL) {
					pCur->prev->next = NULL;
				}

				/*
				 * Remove from others positions
				 */
				else {
					pCur->prev->next = pCur->next;
					pCur->next->prev = pCur->prev;
				}
			}

			pCur = pCur->next;
		}
	}

	/*
	 * Method reverse a Double Linked List
	 */
	void reverse() {

		/*
		 * Check if list is empty
		 */
		if (pHead == NULL) {
			cout << "List is empty" << endl;
			return;
		} else {
			Node *pt = pHead;
			Node *ptr = pHead->next;

			while (ptr != NULL) {
				prepend(ptr->data);
				ptr = ptr->next;
			}

			while (pt->next != NULL) {

				Node *pDel = pt->next;
				if (pDel->next == NULL) {
					pt->next = NULL;
					delete pDel;
				} else {
					pt->next = pDel->next;
					pDel->next->prev = pt;
					delete pDel;
				}
			}

			/* free pt */
			pt = pt->next;
		}
	}
};

int main() {

	DoubleLinkedList l1;
	l1.prepend(3);
	l1.prepend(44);
	l1.prepend(44);
	l1.prepend(4);
	l1.pospend(44);
	l1.pospend(99);
	l1.prepend(44);
	l1.prepend(45);
	l1.display();
	l1.insert(10, 1);
	l1.display();

	DoubleLinkedList l2;
	l2.pospend(3);
	l2.pospend(4);
	l2.pospend(3);
	l2.pospend(2);
	l2.pospend(7);
	l2.pospend(3);
	l2.pospend(1);
	l2.pospend(8);
	l2.pospend(3);
	cout << endl << "L2 before remove :" << endl;
	l2.display();
	cout << "Remove all node->data == 3" << " , after remove : " << endl;
	l2.remove(3);
	l2.display();

	cout << endl;
	DoubleLinkedList l3;
	l3.pospend(1);
	l3.pospend(2);
	l3.pospend(3);
	l3.pospend(4);
	cout << "Before reverse :  ";
	l3.display();
	l3.reverse();
	cout << "After reverse :  ";
	l3.display();
	return 0;
}

/*
 *
 *
 *
 *
 *
 */
